package tree.递归;

import po.ListNode;
import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N有序链表转换二叉搜索树109.java
 * @Description TODO https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 * @createTime 2021年03月31日 13:04:00
 */
public class N有序链表转换二叉搜索树109 {

    /**
     * 有两种方式
     * todo 1. 分治递归的方式，找到链表的中间节点，然后左边为左子树，右边为右子树，一次递归左子树和右子树  复杂度为nlogn
     * todo 2. 分治+中序遍历的方式，类似于有序数组转化为二叉搜索树的方式。先计算链表的长度，然后按照数组的方式来进行处理 复杂度 n
     */
    ListNode globalHead;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        this.globalHead = head;
        int length = countLength(head);
        return buildTree(0, length - 1);
    }

    private TreeNode buildTree(int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(0);
        root.left = buildTree(start, mid - 1);
        root.val = globalHead.val;
        globalHead = globalHead.next;
        root.right = buildTree(mid + 1, end);
        return root;
    }

    private int countLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}
